1. Field of the Invention
The present invention relates generally to systems and methods for processing digital data. In particular, it pertains to a system and method for performing continuous computation of wavelet transforms and can be applied to compression of individual gray scale and color images and key-frame video, for example.
2. Description of the Related Art
The need for reliable and efficient image processing has increased dramatically, particularly in the area of transmission of video, television signals, and other large-size data files. While wide-band Internet connections make it easier to transmit such information over a network, it is still a goal of developers to reduce the amount of bandwidth required to reliably conduct such transmissions.
One method of simplifying image processing is to use data compression techniques. Well-known examples of data compression techniques include Joint Photography Experts Group (JPEG) and Motion Picture Experts Group (MPEG) compression. These methods of encoding and decoding realtime video data, while better than their predecessors, are generally not capable of sufficient bandwidth reduction or are susceptible to excessive data loss in a noisy environment JPEG 2000 is an improvement over the JPEG compression method described above. JPEG 2000 compression makes use of the well-known concept of wavelet transforms to perform the compression. Wavelet transforms, described simply, involve the algorithmic transformation of an image into multiple frequency bands, with each frequency band containing the image at a quarter resolution of the original image, in varying degrees of image quality. As the band progresses from a low frequency to a high frequency, the image quality increases. Since the lowest frequency band is generally the most important band for visual sensitivity, the lowest frequency band is typically the first band transmitted, and the highest frequency band will typically be transmitted last. In this way, if only the lowest frequency band is received, the major features of the image will be visible even though the details contained in the higher frequency band are unavailable.
There are numerous wavelet transforms for transforming image data to handle image processing/compression, each of which, in their basic form, comprise a formula or series of formulas to which the image data is applied. Many examples and explanations of wavelet transforms can be found in patents and in the literature. See, for example, U.S. Pat. No. 6,178,269 to Acharya, U.S. Pat. No. 6,125,210 to Yang, Marcellin et al., “An Overview of JPEG-2000,” Proc. Of IEEE Data Compression Conference, pp. 523-541 (2000); and Sadowsky, J., “Investigation of Signal Characteristics Using the Continuous Wavelet Transform,” Johns Hopkins APL Technical Digest, Vol. 17, No. 3 (1996), each of which are incorporated fully herein by reference.
One example of a well-known wavelet transform is the “integer 5-3” wavelet transform. The 5-3 wavelet transform has very low complexity, provides the best lossless compression, and exhibits a minimum of ringing when quantized. The formula for the 5-3 wavelet transform is as follows:
      [                  (                              (                                          C                1                            +                              C                2                                      )                    ×                      1            2                          )            -              C        3              ]    +      [                  (                              (                                          C                3                            +                              C                4                                      )                    ×                      1            2                          )            -              C        5              ]  where C1 is the value of the first byte in a 5-byte sequence, C2 is the value of the second byte in the 5-byte sequence, C3 is the value of the third byte in the 5-byte sequence, C4 is the value of the fourth byte in the 5-byte sequence, and C5 is the value of the fifth byte in the 5-byte sequence. The first five bytes of a data sequence are processed using this algorithm, then another byte is moved in (and the first byte is moved out) so that the byte that originally occupied the first-byte position is bumped out, the byte that originally occupied the second-byte position is bumped up to the first-byte position, etc.
This process continues until all of the bytes of the image or data file being compressed have been subjected to the algorithm. As each five-byte sequence is processed according to the algorithm, and a transformed version of the first byte in the five-byte sequence is output for display or storage. Once all of the bytes have been processed, a transformed version of the entire image exists.
Many other wavelet transforms are known, each with their own benefits and drawbacks. For example, the “Daubechies 9-7” wavelet transform is another popular algorithm that provides high performance at low bit rates, but with a substantial increase in complexity. Instead of processing the data 5 bits at a time, as is done with the 5-3 wavelet transform, 9 bits are processed at a time in the 9-7 wavelet transform. Both filters provide for multi-resolution extraction and are responsible for much of the substantial quality improvement in JPEG 2000 over the original JPEG.
Although the data being compressed and decompressed using JPEG and JPEG 2000 consists of a series of individual data bytes (e.g., each data byte representing a single pixel in a graphic image), prior art systems process this data in blocks or sub-blocks, primarily because they typically use a Discrete Cosine Transform (DCT) to perform a digital transform, and a DCT requires that the data be processed in blocks. These data blocks, e.g., an 8×8 pixel sub-block taken from a larger 800×600 pixel block forming an entire image, are processed by a computer which computes the wavelet transform using the wavelet transform formula for each sub-block. Since wavelet transforms comprise a sequence of mathematical computations being performed on each byte of data, numerous read, process, and store operations must be performed for each byte, requiring significant processing power and storage capability. This process is repeated for each byte of each sub-block until the processed image data for the entire block (and thus the entire image) is stored in memory. Once the entire block has been processed it can then be utilized for its intended purpose. While this functions fairly well, the prior art method is inefficient and costly. The prior art method requires computers and/or digital signal processors (DSPs) and thus requires significant computing power to perform the algorithm, store the data, and save/display the data.
Accordingly, it would be desirable to have a simpler method for computing wavelet transforms on data that does not require the significant computing power of the prior art.